package com.le.medium.class5;

import org.junit.Test;

import java.util.Arrays;

/**
 * 字符串只由'0'和'1'两种字符构成，
 * 当字符串长度为1时，所有可能的字符串为"0"、"1"；
 * 当字符串长度为2时，所有可能的字符串为"00"、"01"、"10"、"11"；
 * 当字符串长度为3时，所有可能的字符串为"000"、"001"、"010"、"011"、"100"、 "101"、"110"、"111" ...
 * 如果某一个字符串中，只要是出现'0'的位置，左边就靠着'1'，这样的字符串叫作达 标字符串。
 * 给定一个正数N，返回所有长度为N的字符串中，达标字符串的数量。
 * 比如，N=3，返回3，因为只有"101"、"110"、"111"达标。
 * <p>
 * <p>
 * 思路：
 * 枚举前几项发现规律，斐波那契数列
 */
public class Problem01_ZeroLeftOneStringNumber {

    // 时间复杂度O(n),空间复杂度O(n)
    public static int getNum1(int n) {
        if (n < 0) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return n;
        }
        int[] arr = new int[n];
        arr[0] = 1;
        arr[1] = 2;
        for (int i = 2; i < arr.length; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr[n - 1];
    }

    // 时间复杂度o(n), 空间复杂度O(1)
    public static int getNum2(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int pre = 1;
        int cur = 1;
        int temp = 0;
        for (int i = 2; i < n + 1; i++) {
            temp = cur;
            cur += pre;
            pre = temp;
        }
        return cur;
    }

    // 时间复杂度O(log n)
    // 严格递归递推式皆可优化
    public static int getNum3(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return n;
        }
        int[][] base = {
                {1, 1},
                {1, 0}
        };
        int[][] res = matrixPower(base, n - 2);
        return 2 * res[0][0] + res[0][1] ;
    }

    // 求矩阵的p次方
    private static int[][] matrixPower(int[][] m, int p) {
        int[][] res = new int[m.length][m[0].length];
        // 矩阵一次方等于单位矩阵
        // 构建单位矩阵
        for (int i = 0; i < res.length; i++) {
            res[i][i] = 1;
        }
        int[][] temp = m;
        for (; p != 0; p >>= 1) {
            // 最后一个二进位为1
            if ((p & 1) != 0) {
                res = muliMatrix(res, temp);
            }
            // 矩阵一次幂，二次幂，四次幂...
            temp = muliMatrix(temp, temp);
        }
        return res;
    }

    // 矩阵相乘
    public static int[][] muliMatrix(int[][] m1, int[][] m2) {
        int[][] res = new int[m1.length][m2[0].length];
        for (int i = 0; i < m1.length; i++) {
            for (int j = 0; j < m2[0].length; j++) {
                for (int k = 0; k < m2.length; k++) {
                    res[i][j] += m1[i][k] * m2[k][j];
                }
            }
        }
        return res;
    }

    @Test
    public void test() {
        for (int i = 1; i < 20; i++) {
            System.out.print(getNum1(i) + "  ");
            System.out.print(getNum2(i) + "  ");
            System.out.print(getNum3(i));
            System.out.println();
        }
    }

    @Test
    public void test1() {
        int[][] m1 = {
                {1, 2, 0},
                {2, 1, 3}
        };
        int[][] m2 = {
                {2, 3, 0},
                {1, -2, -1},
                {3, 1, 1}
        };
        int[][] res = muliMatrix(m1, m2);
        for (int r = 0; r < res.length; r++) {
            System.out.println(Arrays.toString(res[r]));
        }
    }
}
